class Node:
    def __init__(self, elem =-1,lchild =None,rchild = None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild

class BinaryTree:
    def __init__(self):
        self.root = None
        self.help_queue = []  # 辅助队列

    def level_build_tree(self, node: Node):
        if self.root is None: # 处理根节点
            self.root = node
            self.help_queue.append(node)
        else:
            self.help_queue.append(node)
            if self.help_queue[0].lchild is None:#如果父亲的左节点为空，则将当前节点设为左节点
                self.help_queue[0].lchild = node
            else:
                self.help_queue[0].rchild = node #如果父亲的右节点为空，则将当前节点设为右节点
                self.help_queue.pop(0)


    def pre_order(self,current_node: Node):#先序遍历
        if current_node:
            print(current_node.elem,end = "")
            self.pre_order(current_node.lchild)#左子树
            self.pre_order(current_node.rchild)#右子树

    def mid_order(self,current_node:Node):#中序遍历
        if current_node:
            self.mid_order(current_node.lchild)#左子树
            print(current_node.elem, end="")
            self.mid_order(current_node.rchild)#右子树

    def last_order(self,current_node:Node):#后序遍历
        if current_node:
            self.last_order(current_node.lchild)#左子树
            self.last_order(current_node.rchild)#右子树
            print(current_node.elem, end="")

    def level_order(self):
        help_queue = []
        help_queue.append(self.root)
        while help_queue:
            out_node: Node = help_queue.pop(0)
            print(out_node.elem,end=" ")
            if out_node.lchild:
                help_queue.append(out_node.lchild)
            if out_node.rchild:
                help_queue.append(out_node.rchild)



if __name__ == '__main__':
    tree = BinaryTree()
    for i in range(1,11):
        new_node = Node(i) #实例化节点
        tree.level_build_tree(new_node) #构建二叉树
    tree.pre_order(tree.root)
    print()
    tree.mid_order(tree.root)
    print()
    tree.last_order(tree.root)
    print()
    tree.level_order()
    print()